Load balancing is a way of distributing processing and communications activity across a network such that no one device becomes overloaded. Network devices, such as routers may have one or more sets of load-balanced interfaces, such that when one of the sets of load-balanced interfaces may be used to forward data, one of the interfaces from the set of load-balanced interfaces may be selected. The probability of selecting one of N interfaces in the load-balanced set of interfaces should be 1/N. When a router is configured such that one or more of the N load-balanced interfaces to which it may forward data is connected to another router, the routers are considered to be cascaded. In some networks, cascading of routers may be multiple levels deep.
In some existing networks, the characteristics of the load balancing function is such, that when a router, for example, router A, forwards data to another router, for example, router B, via a load-balanced interface, the conditional probability of router B selecting an interface from among N load-balanced interfaces for forwarding the data may not be 1/N. In other words, in such situations, the load-balancing function of a cascaded router may not distribute the load uniformly.
For example, in one existing network, a router with one or more sets of load balanced interfaces may form a set of bits from data in the packet header, for example, source and destination addresses concatenated together. For the sake of simplicity, we refer to this data as H. In the existing network, each router has unrelated data, per router. We refer to the unrelated data as A. The router then performs a polynomial division by a polynomial p to form a result, R, according to
R=(A::H) mod p, where “::” is concatenation. R may then be used to derive an index to an interface table to select one of the load-balanced interfaces on which to forward the packet.
Concatenating A to the front of H is equivalent to adding A×xh to H, where h is the degree of polynomial H. Thus, mathematically, the router may determine R according to: R=(A×xh+H)mod p, which may be used to index an interface table to determine on which of the load-balanced interfaces the packet will be forwarded. Downstream, a second router may determine R2 according to:
R2=(A2×xh+H) mod p, where A2 is the unrelated data of the second router. Suppose A2=A+Z, where “+” is polynomial addition, base 2. Then:
                              R          ⁢                                          ⁢          2                =                              (                                          (                                  A                  +                  Z                                )                            ⁢              ::              ⁢              H                        )                    ⁢          mod          ⁢                                          ⁢          p                                        =                              (                                                            (                                      A                    +                    Z                                    )                                ⁢                                  x                  h                                            +              H                        )                    ⁢          mod          ⁢                                          ⁢          p                                        =                              (                                          A                ×                                  x                  h                                            +                              Z                ×                                  x                  h                                            +              H                        )                    ⁢          mod          ⁢                                          ⁢          p                    
If (z×xh) mod p happens to be 0, then R2=(A×xh+H)mod p=R for all H. In other words, when (z×xh) mod p happens to be 0, then the probability that R=R2 is 1 for all H. Assuming that the upstream router and the downstream router have N load-balanced interfaces, the routers map R and R2 to a number in the range of 1 to N. In the situation where R=R2, both routers will select an interface based on the same number, k, in the range 1 to N. Therefore, R and R2 are not mathematically independent and the cascaded load-balanced interface would not be uniformly selected.
If the upstream router produced a result, A, from R and the downstream router produced a result, B, from R2 and both A and B are in a range of 1 to N, then A and B are mathematically independent if the probability that A equals a value, j, given that B equals, a value i, is 1/N, for all values of i and j in the range of 1 to N. Stated in mathematical terms:P[(B==i|(A==j)]=1/n, for all i and j in the range 1 to N.The routers described above fail to satisfy this condition.